package 剑指offer;

public class p3前n个数字二进制中1的个数 {
    public int[] countBits(int n) {
        //动态规划
        int[] dp=new int[n+1];
        dp[0]=0;

        for (int i = 1; i <=n ; i++) {
            dp[i]=dp[ i&(i-1) ] + 1;
        }
        return dp;
    }


    public int[] countBits1(int n) {
        int[] res=new int[n+1];

        for (int i = 0; i <=n; i++) {
            int num=countOne(i);
            res[i]=num;
        }
        return res;
    }

    private int countOne(int n) {
        int count=0;
        while (n!=0) {
            if((n&1) ==1) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
}
